Theory of Computation
Q221.
Consider the following languages. L1 = {\ltM\gt |M takes at least 2016 steps on some input}, L2 = {\ltM\gt| M takes at least 2016 steps on all inputs g} and L3 = {\ltM|M accepts \varepsilon}, where for each Turing machine M, \ltM\gt denotes a specific encoding of M. Which one of the following is TRUE?Q223.
Consider the following problems. L(G) denotes the language generated by a grammar G. L(M) denotes the language accepted by a machine M. (I) For an unrestricted grammar G and a string w, whether w\in L(G) (II) Given a Turing machine M, whether L(M) is regular (III) Given two grammars G1 and G2, whether L(G1) = L(G2) (IV) Given an NFA N, whether there is a deterministic PDA P such that N and P accept the same language. Which one of the following statements is correct?Q224.
Which of the following languages are undecidable? Note that \left \langle M \right \rangle indicates encoding of the Turing machine M. L_1=\{\left \langle M \right \rangle|L(M)=\varnothing \} L_2={\left \langle M,w,q \right \rangle|M on input w reaches state q in exactly 100 steps} L_3=\{\left \langle M \right \rangle|L(M) \;is \; not \; recursive\} L_4=\{\left \langle M \right \rangle|L(M) \;contains \; at \; least\; 21 \; members\}Q225.
For a Turing machine M, < M > denotes an encoding of M. Consider the following two languages. \begin{array}{ll} L1 = \{ \langle M \rangle \mid M \text{ takes more than } 2021 \text{ steps on all inputs} \} \\ L2 = \{ \langle M \rangle \mid M\text{ takes more than } 2021 \text{ steps on some input} \} \end{array} Which one of the following options is correct?Q226.
Let A and B be infinite alphabets and let # be a symbol outside both A and B. Let f be a total functional from A* to B*. We say f is computable if there exists a Turning machine M which given an input x in A*, always halts with f(x) on its tape. Let L_{f} denote the language {x#f(x)|x\inA*}. Which of the following statements is true:Q227.
Consider the following statements. I. The complement of every Turing decidable language is Turing decidable II. There exists some language which is in NP but is not Turing decidable III. If L is a language in NP, L is Turing decidable Which of the above statements is/are true?Q228.
Let \lt M \gt be the encoding of a Turing machine as a string over \Sigma={0,1}. Let L = { \lt M \gt |M is a Turning machine that accepts a string of length 2014}. Then, L isQ230.
Which of the following statements is/are FALSE? 1. For every non-deterministic Turing machine, there exists an equivalent deterministic Turing machine. 2. Turing recognizable languages are closed under union and complementation. 3. Turing decidable languages are closed under intersection and complementation. 4. Turing recognizable languages are closed under union and intersection.